Description

给定一张 $n$ 个点 $m$ 条边的图，一条边 $(u,v)$ 有 $\frac{1}{3}$ 的概率消失，$\frac{1}{3}$ 的概率定向成 $u\rightarrow v$ ，$\frac{1}{3}$ 的概率定向成 $v\rightarrow u$ 。求最后的图是 $\rm{DAG}$ 的概率。

$n\leq 20,m\leq \frac{n(n-1)}{2}$

Solution

一个不会整数划分的 sb 的自救

考虑一个这样的问题：给定 $n,m$ ，求将 $m$ 划分成不超过 $n$ 个从 $1$ 开始值域连续的整数的和的方案数。

有一个很明显的做法：设 $f_{i,j,k}$ 表示用了 $i$ 个数，总和为 $j$ ，目前最大数为 $k$ 的方案数。转移比较明显：

Description

$\text{Link}$

Solution

西哥挖坟挖出来一道神仙题。

笛卡尔树是个神仙东西。
$\text{Daniel}$ 神仙出了两道相关的题目，两道题目都巧妙地运用了笛卡尔树的优异性质。
这里总结一下关键的内容。

Description

给定 $n, d_1, d_2$ ，请在 $2n\times 2n$ 的网格中找到 $n^2$ 个点，满足任意两点间的距离的平方既不为 $d_1$ 也不为 $d_2$ 。
注意网格的横纵坐标范围是 $[0,2n)$ 。
$1\leq n\leq 300,1\leq d_1,d_2\leq 2\times 10^5$

Description

$\text{Link}$

Solution

网络流解方程。

刚了一道题超级久...最后 solution 给的做法是 FWT 。觉得做法还挺妙的。
顺带讲讲对 FWT 的理解，怕自己又不记得了。

原理

Description

给定两个 $1\sim n$ 的排列 $p$ 和 $q$ ，其中有些位置未知，用 $0$ 表示。
定义两个排列之间的相似度是：每次从 $p$ 中选择两个元素交换，使其变成 $q$ 的最小次数。
现在要求不全这两个序列，求出对于 $i\in [0,n-1]$ ，补全后相似度为 $i$ 的方案数。

Description

给定长度为 $n$ 的序列 $\{a\}$ ，求 $\{a\}$ 有多少种排列，满足任意相邻两个数的乘积不是完全平方数。
答案对 $10^9+7$ 取模。
$n\leq 300$

Description

有 $n$ 个物品，每个物品有一个权值 $w_i$ 。
现在你需要把这 $n$ 个物品划分成 $k$ 个非空集合。
定义在一个划分下物品的价值为权值和所在集合大小的乘积，一个划分的价值为所有物品的价值之和。